#include "bgi.h"

static color_t BorderColor = 0;
static coord_t UpXLimit    = 0;
static coord_t UpXLimit1   = 0;

typedef point_t _far *stack_point_t_ptr;

struct Stack
{
  stack_point_t_ptr ptr;
  stack_point_t_ptr begin;
  stack_point_t_ptr end;
};

typedef struct Stack _far *StackPtr;

static bool_t StackEmpty(StackPtr stack)
{
  return(stack->ptr == stack->begin);
}

static void StackPush(StackPtr stack, point_t point)
{
  *stack->ptr++ = point;
}

static void StackPop(StackPtr stack)
{
  --stack->ptr;
}

static stack_point_t_ptr StackTop(StackPtr stack)
{
  return(stack->ptr - 1);
}

static bool_t StackRemove(StackPtr stack, point_t point)
{
  stack_point_t_ptr p;
  for(p = stack->begin; p != stack->ptr; ++p)
    if((p->x == point.x) && (p->y == point.y))
    {
      *p = *--stack->ptr;
      return(true);
    }
  return(false);
}

static point_t make_point(coord_t x, coord_t y)
{
  point_t p;
  p.x = x;
  p.y = y;
  return(p);
}

static coord_t ScanDownForBorder(coord_t x, coord_t y)
{
  for( ; x >= vp.x1; --x)
    if(GetPixel(x, y) == BorderColor)
      break;
  return(x + 1);
}

static coord_t ScanUpForBorder(coord_t x, coord_t y)
{
  for( ; x <= vp.x2; ++x)
    if(GetPixel(x, y) == BorderColor)
      break;
  return(x - 1);
}

static coord_t ScanUpForNotBorder(coord_t x, coord_t xmax, coord_t y)
{
  for( ; x <= xmax; ++x)
    if(GetPixel(x, y) != BorderColor)
      return(x);
  return(-1);
}

static bool_t PopPoint(StackPtr stack, int x, int y, int DeltaY)
{
  return(StackRemove(stack, make_point(DeltaY < 0 ? ~x : x, y)));
}

static void PushPoint(StackPtr stack, coord_t x, coord_t maxx, coord_t y, int DeltaY)
{
  while((x = ScanUpForNotBorder(x, maxx, y)) >= 0)
  {
    StackPush(stack, make_point(DeltaY >= 0 ? x : ~x, y));
    x = ScanUpForBorder(x, y) + 1;
  }
}

void PatBarLine(coord_t y, coord_t x1, coord_t x2);

static void Scanner(StackPtr stack, coord_t x, coord_t y, coord_t DeltaY)
{
  coord_t ny, lx;
  do
  {
    ny = y + DeltaY;
    if((ny < vp.y1) || (ny > vp.y2))
      break;
    if(GetPixel(x, ny) != BorderColor)
      lx = ScanDownForBorder(x, ny);
    else if((lx = ScanUpForNotBorder(x, UpXLimit, ny)) < 0)
      break;
    UpXLimit1 = UpXLimit;
    UpXLimit = ScanUpForBorder(lx, ny);
    PatBarLine(ny, lx, UpXLimit);
    PushPoint(stack, lx, x - 1, y, -DeltaY);
    if(UpXLimit1 != UpXLimit)
    {
      coord_t i, j, x1, x2, dy;
      if(UpXLimit1 <= UpXLimit)
      {
        x1 = UpXLimit;
        x2 = UpXLimit1;
        dy = DeltaY;
      }
      else
      {
        x1 = UpXLimit1;
        x2 = UpXLimit;
        dy = -DeltaY;
        y = ny;
      }
      if((j = ScanUpForBorder(i = x1, y)) > x1)
      {
        while((j = ScanUpForBorder(i = j, y + dy)) > i &&
              (j = ScanUpForBorder(i = j, y)) > i) ;
        PushPoint(stack, x1 + 1, i, y + dy, dy);
      }
      PushPoint(stack, x2 + 1, i, y, -dy);
    }
  } while(PopPoint(stack, x = lx, y = ny, -DeltaY) == 0);
}

static void FloodFill2(StackPtr stack, coord_t x, coord_t y, color_t color)
{
  int DeltaY = -1;
  BorderColor = color;
  if(GetPixel(x, y) != BorderColor)
  {
    StackPush(stack, make_point(x = ScanDownForBorder(x, y), y));
    UpXLimit = ScanUpForBorder(x, y);
    while(1)
    {
      Scanner(stack, x, y, DeltaY);
      do
      {
        if(StackEmpty(stack))
          return;
        x = StackTop(stack)->x;
        y = StackTop(stack)->y;
        StackPop(stack);
        if(x >= 0)
        {
          DeltaY = 1;
        }
        else
        {
          DeltaY = -1;
          x = ~x;
        }
        UpXLimit1 = UpXLimit;
        UpXLimit = ScanUpForBorder(x, y);
        PatBarLine(y, x, UpXLimit);
      } while(PopPoint(stack, x, y, -DeltaY) != 0);
    }
  }
}

void FloodFill(coord_t x, coord_t y, color_t color)
{
  point_t stackStorage[512];
  struct Stack stack;
  stack.ptr = stack.begin = (stack_point_t_ptr)&stackStorage[0];
  stack.end = (stack_point_t_ptr)&stackStorage[sizeof(stackStorage) / sizeof(stackStorage[0])];
  FloodFill2(&stack, x, y, color);
}
